package com.jsurf;

//import edu.cicese.ans.Match;

import com.OpenSURF.OpenSurf;
import com.kdtree.KDNode;
import com.kdtree.KDTree;
import edu.cicese.ans.Utilities;
import edu.cicese.ans.Match;
import org.json.simple.JSONArray;
import org.json.simple.JSONObject;
import org.json.simple.JSONValue;

import javax.imageio.ImageIO;
import javax.swing.ImageIcon;
import javax.swing.JFrame;
import javax.swing.JLabel;
import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.FileFilter;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.FilenameFilter;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.nio.ByteBuffer;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Calendar;
import java.util.Collections;
import java.util.Date;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

import static name.audet.samuel.javacv.jna.cv.CV_BGR2GRAY;
import static name.audet.samuel.javacv.jna.cv.cvCvtColor;
import static name.audet.samuel.javacv.jna.cxcore.*;

public class SurfUtil {
	
	public static Map<String, Points> storedPOIs = new HashMap<String, Points>();
	public static HashMap<String, ArrayList<InterestPoint>> clusters = new HashMap<String, ArrayList<InterestPoint>>();
//	public static Map<String, Points> storedTags = new HashMap<String, Points>();
	public static HashMap<String, HashMap<String, Points>> storedTags = new HashMap<String, HashMap<String, Points>>();
	public static List<List<InterestPoint>> sequence = new ArrayList<List<InterestPoint>>();

	public static float total = 0, totalResponses = 0, totalDxx = 0, totalDxy = 0, totalDyy = 0;

	// kd-Tree
	private static final int KDTREE_BBF_MAX_NN_CHKS = 200;
	private static final double NN_SQ_DIST_RATIO_THR = 0.39;
	
	// 7 x 7 Discrete Gaussian Distribution
	public static final double[][] GAUSS25 = {
		{ 0.02546481, 0.02350698, 0.01849125, 0.01239505, 0.00708017, 0.00344629, 0.00142946 },
		{ 0.02350698, 0.02169968, 0.01706957, 0.01144208, 0.00653582, 0.00318132, 0.00131956 },
		{ 0.01849125, 0.01706957, 0.01342740, 0.00900066, 0.00514126, 0.00250252, 0.00103800 },
		{ 0.01239505, 0.01144208, 0.00900066, 0.00603332, 0.00344629, 0.00167749, 0.00069579 },
		{ 0.00708017, 0.00653582, 0.00514126, 0.00344629, 0.00196855, 0.00095820, 0.00039744 },
		{ 0.00344629, 0.00318132, 0.00250252, 0.00167749, 0.00095820, 0.00046640, 0.00019346 },
		{ 0.00142946, 0.00131956, 0.00103800, 0.00069579, 0.00039744, 0.00019346, 0.00008024 }
	};

	public static final float PI = 3.14159f;
	
	public static IplImage getIplImage(String imgFilename) {
		try {
			File imgFile = new File(imgFilename);
			
			BufferedImage bufferedImage = ImageIO.read(imgFile);
			int width = bufferedImage.getWidth();
			int height = bufferedImage.getHeight();
			int [] pixels = new int[width * height];
			bufferedImage.getRGB(0, 0, width, height, pixels, 0, width);
			IplImage iplImg = cvCreateImage(cvSize(width, height), IPL_DEPTH_8U, 3);
			
			
			
			int intVal;
			byte r, g, b;
			
			for (int y = 0; y < height; y++) {
				for (int x = 0; x < width; x++) {
					intVal = pixels[x + y * width];
					r = (byte)(intVal >> 16)/* & 0xFF*/;
					g = (byte)(intVal >> 8)/* & 0xFF*/;
					b = (byte)intVal/* & 0xFF*/;
					//val = r + g + b;
					
					ByteBuffer bb = iplImg.getByteBuffer();
					bb.put(y * iplImg.widthStep + x * iplImg.nChannels + 0, b); //B
					bb.put(y * iplImg.widthStep + x * iplImg.nChannels + 1, g); //G
					bb.put(y * iplImg.widthStep + x * iplImg.nChannels + 2, r); //R
				}
			}
			return iplImg;
			
		} catch(Exception e) {
			e.printStackTrace();
		}
		return null;
	}
	
//	public static IplImage getIplImage2(String imgFilename) {
//		try {
//			File imgFile = new File(imgFilename);
//			IplImage iplImg = IplImage.createFrom(ImageIO.read(imgFile));
//			return iplImg;
//		} catch(Exception e) {
//			e.printStackTrace();
//		}
//		return null;
//	}
	
	//! Convert image to single channel 32F
	public static IplImage getGray(IplImage img) {

		IplImage gray8, gray32;		
		gray32 = cvCreateImage(cvGetSize(img), IPL_DEPTH_32F, 1);
		
		if (img.nChannels == 1) {
			gray8 = img.clone();
		}
		else {
			gray8 = cvCreateImage(cvGetSize(img), IPL_DEPTH_8U, 1);
			cvCvtColor(img, gray8, CV_BGR2GRAY);
		}
		
		cvConvertScale(gray8, gray32, 1.0 / 255.0, 0);
		cvReleaseImage(gray8.pointerByReference());
		
		return gray32;
	}
	
	//! Computes the sum of pixels within the rectangle specified by the top-left start co-ordinate and size
	public static float BoxIntegral(IntegralImage img, int row, int col, int rows, int cols){
		//  A +--------+ B
		//    |        |        A(row, col)
		//  C +--------+ D

		int height = img.getHeight();
		int width = img.getWidth();
		
		// The subtraction by one for row/col is because row/col is inclusive.
		int r1 = Math.min(row, height) - 1;
		int c1 = Math.min(col, width) - 1;
		int r2 = Math.min(row + rows, height) - 1;
		int c2 = Math.min(col + cols, width) - 1;

		float A = (r1 >= 0 && c1 >= 0) ? img.getValueAt(c1, r1) : 0;
		float B = (r1 >= 0 && c2 >= 0) ? img.getValueAt(c2, r1) : 0;
		float C = (r2 >= 0 && c1 >= 0) ? img.getValueAt(c1, r2) : 0;
		float D = (r2 >= 0 && c2 >= 0) ? img.getValueAt(c2, r2) : 0;
	
		return Math.max(0F, D - B - C + A);
	}
	
	public static List<InterestPoint> getInterestPoints(String imagePath, float threshold) {
//		Surf.HESSIAN_THRESHOLD = threshold;
//		return new Surf(imagePath).getFreeOrientedInterestPoints();

		return OpenSurf.getInterestPoints(imagePath, threshold);
	}

	/**
	 * Compares two lists of {@code InterestPoint} objects and
	 * returns a {@code Map} with only those points that matched
	 * in a reverse comparison.
	 *
	 * @param ipts1 the first list of interest-points to compare
	 * @param ipts2 the second list of interest-points to compare
	 * @return a {@code Map} with the matches interest-points
	 */
	public static Map<InterestPoint, InterestPoint> getMatches(List<InterestPoint> ipts1, List<InterestPoint> ipts2) {
		
		Map<InterestPoint, InterestPoint> matchedPoints1 = findMatches(ipts1, ipts2);
		Map<InterestPoint, InterestPoint> matchedPoints2 = findMatches(ipts2, ipts1);

		// take only those points that matched in the reverse comparison too
		Map<InterestPoint, InterestPoint> matchedPoints = new HashMap<InterestPoint, InterestPoint>();
		for (InterestPoint ipt1 : matchedPoints1.keySet()) {
			InterestPoint ipt2 = matchedPoints1.get(ipt1);
			if (ipt1 == matchedPoints2.get(ipt2))
				matchedPoints.put(ipt1, ipt2);
		}
		return matchedPoints;
	}

	/**
	 * Compares two lists of {@code InterestPoint} objects using the
	 * sign of laplacian and a linear nearest neighbor search, and
	 * creates a {@code Map} with the matched interest-points.
	 *
	 * @param ipts1 the first list of interest-points to compare
	 * @param ipts2 the second list of interest-points to compare
	 * @return a {@code Map} with the matches interest-points
	 */
	public static Map<InterestPoint, InterestPoint> findMatches(List<InterestPoint> ipts1, List<InterestPoint> ipts2) {
		Map<InterestPoint, InterestPoint> res = new HashMap<InterestPoint, InterestPoint>();
		float dist, d1, d2;
		InterestPoint bestMatch;
		int descSize = 64;
		float delta;
		float[] v1, v2;

		for (InterestPoint p1 : ipts1) {
			d1 = d2 = Float.MAX_VALUE;
			bestMatch = null;

			ipts2Loop: for (InterestPoint p2 : ipts2) {
				// Compare descriptors (based on calculating of squared dist between two vectors)
				dist = 0;
				v1 = p1.getDescriptor();
				v2 = p2.getDescriptor();
				for (int i = 0; i < descSize; i++) {
					delta = v1[i] - v2[i];
					dist += delta * delta;
					if (dist >= d2)
						continue ipts2Loop;
				}
//				dist = (float)Math.sqrt(dist);
//				System.out.println("Best dist: " + dist);
				if (dist < d1) {
					d2 = d1;
					d1 = dist;
					bestMatch = p2;
				} else { // dist < d2
					d2 = dist;
				}

			}

//			System.out.println("Best dist: " + (d1/d2));

			// Threshold values in other implementations:
			// OpenSURF:                    0.65
			// OpenCV-2.0.0 (find_obj.cpp): 0.6
			// Orig. SURF:                  0.5

//			System.out.println("test point: x=" + p1.getX() + ", y=" + p1.getY());
//			System.out.println("Best match: x=" + bestMatch.getX() + ", y=" + bestMatch.getY() + ", d=" + d1);
			if (d1 < 0.65f * d2) {
				// Matching point found.
				res.put(p1, bestMatch);
				// Store the change in position (p1 -> p2) into the matchingPoint:
//				bestMatch.setDx(bestMatch.getX() - p1.getX());
//				bestMatch.setDy(bestMatch.getY() - p1.getY());
			}
		}
		return res;
	}
	
	//! Matches the image (poi file) against the tags (inside a specific spaceID/location)
	//TODO: If it's needed to send back only one tagID, then remove the JSONArray.
	@SuppressWarnings("unchecked")
	public static String[] getTags(List<InterestPoint> points, /*String spaceID, */int spacesToSearch) {
		Utilities.print("Starting tag matching proccess.");

		JSONArray jaTags = new JSONArray();
		JSONObject joTag = new JSONObject();
		List<Match> matches = new ArrayList<Match>();

		for (int i = 0; i < spacesToSearch; i++) {
//			String spaceID = Utilities.userLocations[i];
			String spaceID = "01";
			for (Entry<String, Points> entry : storedTags.get(spaceID).entrySet()) {
				if (isAvailable(entry.getKey(), spaceID)) {
					Map<InterestPoint, InterestPoint> matchedPoints = getMatches(points, entry.getValue().points);
					matches.add(new Match(matchedPoints, entry.getKey(), spaceID));
//				matches.add(new Match(matchedPoints.size(), entry.getKey(),
//                          toInterestPointList(matchedPoints.keySet().toArray())));
				}
			}
		}

	  	Collections.sort(matches);

		joTag.put("tagID", "000");

		String matchSpaceID = "00";

		// perform a scale consistency check on the matched points
		if (!matches.isEmpty() && matches.get(0).quantity >= Utilities.minPoiMatched) {
			ArrayList<Map<InterestPoint, InterestPoint>> matchesPruned =
					ScaleConsistencyCheck.compute(matches.get(0).matches);
			if (matchesPruned.get(0).size() >= Utilities.minPoiMatched) {
				Utilities.print(matchesPruned.get(0).size() + " points matched.");
				joTag.put("tagID", matches.get(0).filename);
				joTag.put("area", getCoordinates(matchesPruned.get(0).keySet()));
				joTag.put("fps", getFPSCoordinates(matchesPruned.get(1).keySet()));
//				jaTags.add(joTag);

				matchSpaceID = matches.get(0).spaceID;
			}
		}

		jaTags.add(joTag);

		///////////
		//Save log
		Utilities.saveString(Utilities.imagePath + Utilities.imageName + "_"
				+ matchSpaceID + " " + joTag.get("tagID"), "");
		///////////

//		jaTags.toJSONString();
		return new String[]{jaTags.toJSONString(), matchSpaceID};
	  	
//	  	for (int x = 0; x < 5 && x < matches.size(); x++) {
//			jaTags.add(matches.get(x).filename);
//			System.out.println(matches.get(x).filename + ": " + matches.get(x).quantity);
//		}
		/*if (!storedTags.isEmpty() && matches.get(0).quantity >= Utilities.minPoiMatched) {
//			System.out.println(matches.get(0).quantity + " points matched.");
			Utilities.print(matches.get(0).quantity + " points matched.");
			joTag.put("tagID", matches.get(0).filename);
			joTag.put("area", getCoordinates(matches.get(0).points));
			jaTags.add(joTag);
		}
		else {
			joTag.put("tagID", "000");
			jaTags.add(joTag);
		}

	  	return jaTags.toJSONString();*/
	}

	@SuppressWarnings("unchecked")
	public static String[] getTagsAll(List<InterestPoint> points) {
		Utilities.print("Starting tag matching proccess.");

		JSONArray jaTags = new JSONArray();
		JSONObject joTag = new JSONObject();
		List<Match> matches = new ArrayList<Match>();


		String spaceID;
		for (Entry<String, HashMap<String, Points>> space : storedTags.entrySet()) {
			spaceID = space.getKey();
			for (Entry<String, Points> entry : space.getValue().entrySet()) {
				if (isAvailable(entry.getKey(), spaceID)) {
					Map<InterestPoint, InterestPoint> matchedPoints = getMatches(points, entry.getValue().points);
					matches.add(new Match(matchedPoints, entry.getKey(), spaceID));
//				matches.add(new Match(matchedPoints.size(), entry.getKey(),
//                          toInterestPointList(matchedPoints.keySet().toArray())));
				}
			}
		}

	  	Collections.sort(matches);

		joTag.put("tagID", "000");

		String matchSpaceID = "00";

		// perform a scale consistency check on the matched points
		if (!matches.isEmpty() && matches.get(0).quantity >= Utilities.minPoiMatched) {
//			Utilities.print(matches.get(0).quantity + " points matched.");
//			joTag.put("tagID", matches.get(0).filename);
//			joTag.put("area", getCoordinates(matches.get(0).matches.keySet()));
//			joTag.put("fps", new JSONArray());

//				matchSpaceID = matches.get(0).spaceID;
			ArrayList<Map<InterestPoint, InterestPoint>> matchesPruned =
					ScaleConsistencyCheck.compute(matches.get(0).matches);
			if (matchesPruned.get(0).size() >= Utilities.minPoiMatched) {
				Utilities.print(matchesPruned.get(0).size() + " points matched.");
				joTag.put("tagID", matches.get(0).filename);
				joTag.put("area", getCoordinates(matchesPruned.get(0).keySet()));
				joTag.put("fps", getFPSCoordinates(matchesPruned.get(1).keySet()));
//				jaTags.add(joTag);

				matchSpaceID = matches.get(0).spaceID;
			}
		}

		jaTags.add(joTag);

		///////////
		//Save log
		Utilities.saveString(Utilities.imagePath + Utilities.imageName + "_"
				+ matchSpaceID + " " + joTag.get("tagID"), "");
		///////////

		return new String[]{jaTags.toJSONString(), matchSpaceID};
	}


	@SuppressWarnings("unchecked")
	public static String getTagsAllTest(List<InterestPoint> points) {
//		Utilities.print("Starting tag matching proccess.");

		JSONArray jaTags = new JSONArray();
		JSONObject joTag = new JSONObject();
		List<Match> matches = new ArrayList<Match>();


		String spaceID;
		for (Entry<String, HashMap<String, Points>> space : storedTags.entrySet()) {
			spaceID = space.getKey();
			for (Entry<String, Points> entry : space.getValue().entrySet()) {
				if (isAvailable(entry.getKey(), spaceID)) {
					Map<InterestPoint, InterestPoint> matchedPoints = getMatches(points, entry.getValue().points);
					matches.add(new Match(matchedPoints, entry.getKey(), spaceID));
//				matches.add(new Match(matchedPoints.size(), entry.getKey(),
//                          toInterestPointList(matchedPoints.keySet().toArray())));
				}
			}
		}

	  	Collections.sort(matches);

		joTag.put("tagID", "000");

		String matchSpaceID = "00";

		String tagID = "000";
		int found = 0;
		int accepted = 0;
		int total = 0;
		JSONObject coords = new JSONObject();

		// perform a scale consistency check on the matched points
		if (!matches.isEmpty() && matches.get(0).quantity >= Utilities.minPoiMatched) {
			matchSpaceID = matches.get(0).spaceID;
			tagID = matches.get(0).filename;
			total = matches.get(0).quantity;
//			Utilities.print(matches.get(0).quantity + " points matched.");
//			joTag.put("tagID", matches.get(0).filename);
//			joTag.put("area", getCoordinates(matches.get(0).matches.keySet()));
//			joTag.put("fps", new JSONArray());

//				matchSpaceID = matches.get(0).spaceID;
			ArrayList<Map<InterestPoint, InterestPoint>> matchesPruned =
					ScaleConsistencyCheck.compute(matches.get(0).matches);
			accepted = matchesPruned.get(0).size();
			if (matchesPruned.get(0).size() >= Utilities.minPoiMatched) {
//				Utilities.print(matchesPruned.get(0).size() + " points matched.");
				joTag.put("tagID", matches.get(0).filename);
				coords = getCoordinates(matchesPruned.get(0).keySet());
//				joTag.put("area", getCoordinates(matchesPruned.get(0).keySet()));
				joTag.put("area", coords);
				joTag.put("fps", getFPSCoordinates(matchesPruned.get(1).keySet()));
//				jaTags.add(joTag);


//				matchSpaceID = matches.get(0).spaceID;
//				tagID = matches.get(0).filename;

				accepted = matchesPruned.get(0).size();
				found = 1;
			}
		}

		jaTags.add(joTag);

		///////////
		//Save log
//		String log = Utilities.imageName + " " + matchSpaceID + " " + tagID + " " + found + " " +
//				accepted + " " + total;
		///////////

		///////////
		//Save log
		String log = Utilities.imageName + " " + matches.get(0).spaceID+ " " + matches.get(0).filename + " " + matches.get(1).spaceID + " " +
				matches.get(1).filename + " " + found + " " +
				accepted + " " + matches.get(0).quantity + " " + matches.get(1).quantity + " " + coords;
		///////////

		return log;
	}

	/*//! Matches the image (poi file) against all the tags
	@SuppressWarnings("unchecked")
	public static JSONObject getTags(List<InterestPoint> points) {
//		JSONArray jaTags = new JSONArray();
		JSONObject joTag = new JSONObject();
		
		List<Match> matches = new ArrayList<Match>();
//		System.out.println("Starting tag matching proccess.");
		Utilities.print("Starting tag matching proccess.");

		String entryID, spaceID;
		Points tagPoints;
	  	for (Entry<String, Points> entry : storedTags.entrySet()) {
			entryID = entry.getKey();
			spaceID = entryID.substring(0, 2);
			tagPoints = entry.getValue();
//			System.out.println(entryID);
			if (isAvailable(entryID.substring(2, 5), spaceID)) {
				Map<InterestPoint, InterestPoint> matchedPoints = getMatches(points, tagPoints.points);
//				matches.add(new Match(matchedPoints, entryID, spaceID));
				matches.add(new Match(matchedPoints.size(), entryID, spaceID));
//				System.out.println(matchedPoints.size() + " " + entryID);
			}
		}
	  	Collections.sort(matches);

		ScaleConsistencyCheck.compute(matches.get(0).matches);

//	  	for (int x = 0; x < 5 && x < matches.size(); x++) {
//			jaTags.add(matches.get(x).filename);
//			System.out.println(matches.get(x).filename + ": " + matches.get(x).quantity);
//		}
		if (!storedTags.isEmpty() && matches.get(0).quantity >= Utilities.minPoiMatched) {
//			System.out.println(matches.get(0).quantity + " points matched.");
			Utilities.print(matches.get(0).quantity + " points matched.");
			joTag.put("tagID", matches.get(0).filename.substring(2, 5));
			joTag.put("spaceID", matches.get(0).spaceID);
//			jaTags.add(joTag);
		}
		else {
			joTag.put("tagID", "000");
			joTag.put("spaceID", "00");
//			jaTags.add(joTag);
		}

//	  	return jaTags.toJSONString();
		return joTag;
	}*/

	//! Gets the tag coordinates
	@SuppressWarnings("unchecked")
	private static JSONObject getCoordinates(Set<InterestPoint> points) {
		int minX, minY, maxX, maxY;
		//G2
//		float scaleBigx = 0.875f;
//		float scaleSmallx = 0.6f;
		//Nexus S
		float scaleBigx = 0.9722f;
		float scaleSmallx = 0.6666f;
		//Both
		float scaleSmally = 0.6f;
		float scaleBigy = 0.875f;
		//G2
//		minX = 800;
		//Nexus S
		minX = 720;
		minY = 480;
		//Other
//		minX = 800;
//		minY = 600;
//		scaleBigx = 1f;
//		scaleBigy = 1f;

		maxX = 0;
		maxY = 0;
		int x, y;
		JSONArray jaPoints = new JSONArray();
		JSONObject joPoint;
		for (InterestPoint point : points) {
			joPoint = new JSONObject();
			x = (int)point.getX();
			y = (int)point.getY();
			joPoint.put("x", x);
			joPoint.put("y", y);
			jaPoints.add(joPoint);
			if (x > maxX) maxX = x;
			if (x < minX) minX = x;
			if (y > maxY) maxY = y;
			if (y < minY) minY = y;
		}

		JSONObject joArea = new JSONObject();
		joArea.put("x1", (int)(minX * scaleBigx) - 3);
		joArea.put("y1", (int)(minY * scaleBigy) - 3);
		joArea.put("x2", (int)(maxX * scaleBigx) + 3);
		joArea.put("y2", (int)(maxY * scaleBigy) + 3);
		joArea.put("points", jaPoints);

		joArea.put("xs1", (int)(minX * scaleSmallx) - 3);
		joArea.put("ys1", (int)(minY * scaleSmally) - 3);
		joArea.put("xs2", (int)(maxX * scaleSmallx) + 3);
		joArea.put("ys2", (int)(maxY * scaleSmally) + 3);

		return joArea;
	}

	@SuppressWarnings({"unchecked"})
	public static JSONArray getFPSCoordinates(Set<InterestPoint> points) {
		JSONArray jaPoints = new JSONArray();
		JSONObject joPoint;
		for (InterestPoint point : points) {
			joPoint = new JSONObject();
			joPoint.put("x", (int)point.getX());
			joPoint.put("y", (int)point.getY());
			jaPoints.add(joPoint);
		}
		return jaPoints;
	}

	//! Gets the tag coordinates
	@SuppressWarnings("unchecked")
	private static JSONObject getCoordinates(List<InterestPoint> points) {
		int minX, minY, maxX, maxY;
		float scale = 0.875f;
		minX = 800;
		minY = 480;
		maxX = 0;
		maxY = 0;
		int x, y;
		JSONArray jaPoints = new JSONArray();
		JSONObject joPoint;
		for (InterestPoint point : points) {
			joPoint = new JSONObject();
			x = (int)point.getX();
			y = (int)point.getY();
			joPoint.put("x", x);
			joPoint.put("y", y);
			jaPoints.add(joPoint);
			if (x > maxX) maxX = x;
			if (x < minX) minX = x;
			if (y > maxY) maxY = y;
			if (y < minY) minY = y;
		}

		x = (int)(minX * scale) - 3;
		y = (int)(minY * scale) - 3;
		maxX = (int)(maxX * scale) + 3;
		maxY = (int)(maxY * scale) + 3;
//		int width = (int)((maxX - minX) * scale) + 6;
//		int height = (int)((maxY - minY) * scale) + 6;

		JSONObject joArea = new JSONObject();
		joArea.put("x1", x);
		joArea.put("y1", y);
		joArea.put("x2", maxX);
		joArea.put("y2", maxY);
		joArea.put("points", jaPoints);
//		joArea.put("width", width);
//		joArea.put("height", height);

		return joArea;
	}

	//! Checks if the tag date is correct.
	private static boolean isAvailable(String tagID, String spaceID) {
		String datePath = Utilities.getTagDir(spaceID) + "all\\" + tagID + "\\" + tagID + ".date";
//		System.out.println(datePath);
		if (new File(datePath).exists()) {
			Calendar currentCalendar = Calendar.getInstance();
			Date currentDate = currentCalendar.getTime();
			JSONObject joDate = (JSONObject) JSONValue.parse(Utilities.loadString(datePath));
			if (joDate.get("enabled") != null && !Boolean.valueOf(joDate.get("enabled").toString())) {
				return false;
			}
			int type = Integer.valueOf(joDate.get("type").toString());
			if (type != 0) {
				if (type == 1) {
					// 'Periodic' notification
//					System.out.println("PERIODIC NOTIFICATION");
					JSONArray jaDays = (JSONArray) joDate.get("days");
					if (jaDays.size() != 7) {
						boolean dayMatched = false;
						for (Object jaDay : jaDays) {
							if (getDayOfWeek(Integer.valueOf(jaDay.toString())) ==
									currentCalendar.get(Calendar.DAY_OF_WEEK)) {
//								System.out.println(jaDay.toString() + "=" + getDayOfWeek(Integer.valueOf(jaDay.toString()))
//								+ " vs " + currentCalendar.get(Calendar.DAY_OF_WEEK));
								dayMatched = true;
								break;
							}
						}
						if (!dayMatched) {
							Utilities.print("Unavailable");
							return false;
						}
					}
				}
				else {
					// 'Specific' notification
//					System.out.println("SPECIFIC NOTIFICATION");
					SimpleDateFormat df = new SimpleDateFormat("dd/MM/yyyy");
					try {
						Date d1 = df.parse(joDate.get("date").toString());
						Date d2 = df.parse(df.format(currentDate));
//						System.out.println("Checking " + d1 + " vs " + d2);
						if (!d1.equals(d2)) {
//							System.out.println("Unavailable " + d1 + " vs " + d2);
							return false;
						}
					} catch (ParseException e) { e.printStackTrace(); }
				}
				int timeType = Integer.valueOf(joDate.get("timeType").toString());
				if (timeType == 0) {
					return true;
				}
				else {
					try {
//						System.out.println("CHECKING HOURS");
						SimpleDateFormat df = new SimpleDateFormat("hh:mm");
						Date dBegin = df.parse(joDate.get("begin").toString());
						Date dEnd = df.parse(joDate.get("end").toString());
						String hours = String.valueOf(currentCalendar.get(Calendar.HOUR_OF_DAY));
						String minutes = String.valueOf(currentCalendar.get(Calendar.MINUTE));
						Date dTag = df.parse(hours + ":" + minutes);
//						System.out.println("Checking " + dTag + " vs " + dBegin + " and " + dEnd);
						if ((dTag.after(dBegin) && dTag.before(dEnd)) || dTag.equals(dBegin) || dTag.equals(dEnd)) {
							return true;
						}
//						else {
//							System.out.println("Unavailable " + dTag + " vs " + dBegin + " and " + dEnd);
//						}
					} catch (ParseException e) { e.printStackTrace(); }
				}
			}
			else {
				// 'Always' notification
				return true;
			}
		}
		return false;
 	}

	//! Gets the DAY_OF_THE_WEEK value
	private static int getDayOfWeek(int day) {
		int dayWeek = day + 2;
		if (dayWeek == 8) {
			dayWeek = 1;
		}
		return dayWeek;
	}
	
	//! Performs a matching to locate a user.
	public static void locateUser() {
//		Utilities.userLocation = null;
//		try {
			List<Match> individualMatches, finalMatches;
//    		List<List<InterestPoint>> sequence = new ArrayList<List<InterestPoint>>();
    		Map<String, Match> matches = new HashMap<String, Match>();

			// Check spaceID count
			File spaceDir = new File(Utilities.spaceDir);
			FileFilter spaceFilter = new FileFilter() {
				public boolean accept(File file) {
					return file.isDirectory();
				}
			};
			File[] spaces = spaceDir.listFiles(spaceFilter);
			if (spaces != null) {
				String spaceID;
				Utilities.print(spaces.length + " espacios.");

				for (File space : spaces) {
					spaceID = space.getName();
					matches.put(spaceID, new Match(0, 0, spaceID));
				}

				/*// Load the location poi files (downloaded from the client)
				File locationDir = new File(Utilities.locationDir);
				FilenameFilter poiFilter = new FilenameFilter() {
					public boolean accept(File dir, String name) {
						return name.toLowerCase().endsWith(".poi");
					}
				};
				File[] poiFiles = locationDir.listFiles(poiFilter);
				if (poiFiles != null) {
					for (File poiFile : poiFiles) {
						sequence.add(loadInterestPointListFromFile(poiFile.getCanonicalPath()));
					}
				}*/

				// for each image in the sequence
				for (List<InterestPoint> points : sequence) {
					individualMatches = new ArrayList<Match>();
					// for each stored POI
					for (Entry<String, Points> entry : storedPOIs.entrySet()) {
						Map<InterestPoint, InterestPoint> matchedPoints = getMatches(points, entry.getValue().points);
						individualMatches.add(new Match(matchedPoints.size(), entry.getKey(), entry.getValue().spaceID));
					}

					Collections.sort(individualMatches);

					for (int x = 0; x < 5 && x < individualMatches.size(); x++) {
						Match match = matches.get(individualMatches.get(x).spaceID);
						match.ocurrences++;
						match.quantity += individualMatches.get(x).quantity;
					}
				}

				if (!storedPOIs.isEmpty()) {
					finalMatches = convertToList(matches);
//					Collections.sort(finalMatches);

//					Utilities.print("USER LOCATION: " + finalMatches.get(0).spaceID);

					Utilities.userLocations = new String[finalMatches.size()];
					String log = "USER LOCATION: ";
					int i = 0;

					for (Match match : finalMatches) {
						log += match.spaceID + ": [" + match.quantity + "] ";
						Utilities.userLocations[i] = match.spaceID;
						i++;
					}

					float ratio = 1f;
					if (finalMatches.get(0).quantity >= Utilities.userLocationMinimumStrength ) {
						if (Utilities.userLocations.length > 1) {
							ratio = (float)finalMatches.get(1).quantity / finalMatches.get(0).quantity;
							if (ratio >= Utilities.userLocationRatio) {
								Utilities.userLocations = null;
//							    Utilities.userLocationStrength = 0;
							}
						}
					}
					else {
						Utilities.userLocations = null;
//						Utilities.userLocationStrength = 0;
					}



					Utilities.userLocationStrength = finalMatches.get(0).quantity;
					Utilities.print(log + " -->" + ratio + "<--");

//					Utilities.userLocation = finalMatches.get(0).spaceID;
				}
				else {
					Utilities.print("StoredPOIs vacía. No se puede obtener la ubicación del usuario.");
//					Utilities.userLocation = null;
					Utilities.userLocations = null;
//					Utilities.userLocationStrength = 0;
				}
			}
//		}
//		catch (IOException e) { e.printStackTrace(); }
	}

	/*//! Performs a matching to locate a user.
	public static void locateUserWithClusters() {
		Utilities.userLocation = null;
		try {
			List<Match> individualMatches, finalMatches;
    		List<List<InterestPoint>> sequence = new ArrayList<List<InterestPoint>>();
    		Map<String, Match> matches = new HashMap<String, Match>();

			// Check spaceID count
			File spaceDir = new File(Utilities.spaceDir);
			FileFilter spaceFilter = new FileFilter() {
				public boolean accept(File file) {
					return file.isDirectory();
				}
			};
			File[] spaces = spaceDir.listFiles(spaceFilter);
			if (spaces != null) {
				String spaceID;
				Utilities.print(spaces.length + " espacios.");

				for (File space : spaces) {
					spaceID = space.getName();
					matches.put(spaceID, new Match(0, 0, spaceID));
				}

				// Load the location poi files (downloaded from the client)
				File locationDir = new File(Utilities.locationDir);
				FilenameFilter poiFilter = new FilenameFilter() {
					public boolean accept(File dir, String name) {
						return name.toLowerCase().endsWith(".poi");
					}
				};
				File[] poiFiles = locationDir.listFiles(poiFilter);
				if (poiFiles != null) {
					for (File poiFile : poiFiles) {
						sequence.add(loadInterestPointListFromFile(poiFile.getCanonicalPath()));
					}
				}

				// for each image in the sequence
				for (List<InterestPoint> points : sequence) {
					individualMatches = new ArrayList<Match>();
					// for each stored POI
					for (Entry<String, ArrayList<InterestPoint>> entry : clusters.entrySet()) {
						Map<InterestPoint, InterestPoint> matchedPoints = getMatches(points, entry.getValue());
						individualMatches.add(new Match(matchedPoints.size(),*//* entry.getKey(), *//*entry.getKey()));
					}

					Collections.sort(individualMatches);

					for (int x = 0; x < 5 && x < individualMatches.size(); x++) {
						Match match = matches.get(individualMatches.get(x).spaceID);
						match.ocurrences++;
						match.quantity += individualMatches.get(x).quantity;
					}
				}

				if (!clusters.isEmpty()) {
					finalMatches = convertToList(matches);
//					Collections.sort(finalMatches);

//					System.out.println("USER LOCATION: " + finalMatches.get(0).spaceID);
					Utilities.print("USER LOCATION: " + finalMatches.get(0).spaceID);

					String log = "";
					for (Match match : finalMatches) {
						log += match.quantity + " ";
					}
					Utilities.print(log);

					Utilities.userLocation = finalMatches.get(0).spaceID;
				}
				else {
					Utilities.print("Clusters vacía. No se puede obtener la ubicación del usuario.");
					Utilities.userLocation = null;
				}
			}
		}
		catch (IOException e) { e.printStackTrace(); }
	}*/
	
	//! Loads all the saved POIs from the repository (to locate the user)
	public static void loadPOIs() {
		try {
			Utilities.print("Loading interest points...");
			storedPOIs.clear();
			File spaceDir = new File(Utilities.spaceDir);
			FileFilter spaceFilter = new FileFilter() {
				public boolean accept(File file) {
					return file.isDirectory();
				}
			};
			File[] spaces = spaceDir.listFiles(spaceFilter);
			if (spaces != null) {
				for (File space : spaces) {
					FilenameFilter filter = new FilenameFilter() {
						public boolean accept(File dir, String name) {
							return name.toLowerCase().endsWith(".poi");
						}
					};
					File poiDir = new File(space + "\\pois\\" + Utilities.SERVER_LOC_RES + "\\" +
							Utilities.SERVER_LOC_THRESHOLD + "\\");
					File[] poiFiles = poiDir.listFiles(filter);
					if (poiFiles != null) {
						for (File poiFile : poiFiles) {
							storedPOIs.put(space.getName() + poiFile.getName().substring(0, 3),
									loadPointsFromFile(poiFile.getCanonicalPath()));
						}
					}
				}
			}
			Utilities.print(storedPOIs.size()+ " point lists loaded.");
		}
		catch (IOException e) { e.printStackTrace(); }
	}

	public static void loadClusters() {
		try {
			Utilities.print("Loading clusters...");
			clusters.clear();
			File spaceDir = new File(Utilities.spaceDir);
			FileFilter spaceFilter = new FileFilter() {
				public boolean accept(File file) {
					return file.isDirectory();
				}
			};
			File[] spaces = spaceDir.listFiles(spaceFilter);
			if (spaces != null) {
				for (File space : spaces) {
					ArrayList<InterestPoint> spaceClusters =
							new File(space.getCanonicalPath() + "\\clusters").exists() ?
							loadClusters(space.getCanonicalPath() + "\\clusters") : null;
					if (spaceClusters == null) {
						spaceClusters = new ArrayList<InterestPoint>();
					}
					clusters.put(space.getName(), spaceClusters);
				}
			}
		}
		catch (IOException e) { e.printStackTrace(); }
	}

/*	public static void getClustersAVG() {
//		float sum, avg;
		HashMap<String, ArrayList<float[]>> clustersAVG = new HashMap<String, ArrayList<float[]>>();
		float[] sumDescriptor;
		for (Entry<String, ArrayList<ArrayList<InterestPoint>>> space : clusters.entrySet()) {
			ArrayList<float[]> descriptors = new ArrayList<float[]>();
			for (ArrayList<InterestPoint> metafeature : space.getValue()) {
//				sum = avg = 0;
				sumDescriptor = new float[64];
				for (InterestPoint ip : metafeature) {
					float[] descriptor = ip.getDescriptor();
					for (int i = 0; i < descriptor.length; i++) {
						sumDescriptor[i] += descriptor[i];
						if (i == descriptor.length - 1) {
							sumDescriptor[i] /= metafeature.size();
						}
					}
				}
//				for (int i = 0; i < sumDescriptor.length; i++) {
//					sumDescriptor[i] /= metafeature.size();
//				}
				descriptors.add(sumDescriptor);
			}
			clustersAVG.put(space.getKey(), descriptors);
		}
		saveToFile(clustersAVG, Utilities.spaceDir + "clustersAVG");

	}*/
	
	/*//! Loads all the tags from a specified spaceID
	public static void loadTags(String spaceID) {
		storedTags.clear();
		File tagDir = new File(Utilities.getTagDir(spaceID) + "all\\");
		FileFilter tagFilter = new FileFilter() {
			public boolean accept(File file) {
				return file.isDirectory();
			}
		};
		File[] tags = tagDir.listFiles(tagFilter);

		if (tags != null) {
			for (File tag : tags) {
				Points points = loadPointsFromFile(tag + "\\" + tag.getName() + ".poi");
				if (points != null) {
					storedTags.put(tag.getName(), points);
				}
				else {
//					System.out.println("Missing tag " + tag.getName() + " .poi file.");
					Utilities.print("Missing tag " + tag.getName() + " .poi file.");
				}
			}
		}
	}*/

	//! Loads the tag repository
	public static void loadAllTags() {
		Utilities.print("Loading tags...");
		storedTags.clear();
		HashMap<String, Points> tempMap;
		int c = 0;

		File spaceDir = new File(Utilities.spaceDir);
		FileFilter spaceFilter = new FileFilter() {
			public boolean accept(File file) {
				return file.isDirectory();
			}
		};
		File[] spaces = spaceDir.listFiles(spaceFilter);
		if (spaces != null) {
			for (File space : spaces) {
				tempMap = new HashMap<String, Points>();

				File tagDir = new File(Utilities.getTagDir(space.getName()) + "all\\");
				FileFilter tagFilter = new FileFilter() {
					public boolean accept(File file) {
						return file.isDirectory();
					}
				};
				File[] tags = tagDir.listFiles(tagFilter);
				if (tags != null) {
					for (File tag : tags) {
						Points points = loadPointsFromFile(tag + "\\" + tag.getName() + ".poi");
						if (points != null) {
//							storedTags.put(space.getName() + tag.getName(), points);
							tempMap.put(tag.getName(), points);
							c++;
						}
						else {
							Utilities.print("Missing tag " + tag.getName() + " .poi file.");
						}
					}
				}
				storedTags.put(space.getName(), tempMap);
			}
		}
		Utilities.print(c + " tags loaded.");
	}

	//! Saves an object to a file
	public static void saveToFile(Object object, String filename) {
		try {
			ObjectOutputStream stream = new ObjectOutputStream(new FileOutputStream(new File(filename)));
			stream.writeObject(object);
			stream.close();
		}
		catch (IOException e) { e.printStackTrace(); }
	}
	
	//! Loads the POIs (Points objects) from a file
	public static Points loadPointsFromFile(String filename) {
		try {
			ObjectInputStream str = new ObjectInputStream(new FileInputStream(new File(filename)));
			try {
				return (Points)str.readObject();
			}
			catch (ClassNotFoundException e) { e.printStackTrace(); }
			finally {
				str.close();
			}
		}
		catch (IOException e) { e.printStackTrace(); }
		return null;
	}
	
	//! Loads the POIs (InterestPoint list) from a file
	@SuppressWarnings("unchecked")
	public static List<InterestPoint> loadInterestPointListFromFile(String filename) {
		try {
			ObjectInputStream str = new ObjectInputStream(new FileInputStream(new File(filename)));
			try {
				return (List<InterestPoint>)str.readObject();
			}
			catch (ClassNotFoundException e) { e.printStackTrace(); }
			finally {
				str.close();
			}
		}
		catch (IOException e) { e.printStackTrace(); }
		return null;
//		try {
//			ObjectInputStream str = new ObjectInputStream(new FileInputStream(new File(filename)));
//			return (List<InterestPoint>)str.readObject();
//		}
//		catch (Exception e) { e.printStackTrace(); }
//		return null;
	}

	/**
	 * Loads an {@code ArrayList} of meta-features from a file.
	 *
	 * @param filename the path from the file to load
	 * @return the {@code ArrayList} of meta-features (Clusters) loaded
	 */
	@SuppressWarnings({"unchecked"})
	public static ArrayList<InterestPoint> loadClusters(String filename) {
		try {
			ObjectInputStream str = new ObjectInputStream(new FileInputStream(new File(filename)));
			try {
				return (ArrayList<InterestPoint>)str.readObject();
			}
			catch (ClassNotFoundException e) { e.printStackTrace(); }
			finally {
				str.close();
			}
		}
		catch (IOException e) { e.printStackTrace(); }
		return null;
	}

	//! Loads the changed POIs (since the last update)
	@SuppressWarnings({"unchecked"})
	public static void updatePOIs() {
		Utilities.loadingPOIs = true;
		JSONObject joPOIs = Utilities.loadJSONObject(Utilities.spaceDir + "POIchangelog.ans");
		cleanChangelog("POIchangelog.ans");
		String entryKey, spaceID, poiID, poiPath;
		File poiFile;
//		List<String> POIsToRemove = new ArrayList<String>();

		for (Entry<String, String> entry : (Set<Entry<String, String>>) joPOIs.entrySet()) {
			entryKey = entry.getKey();
			spaceID = entryKey.substring(0, 2);
			poiID = entryKey.substring(2, 5);

			poiPath = Utilities.spaceDir + spaceID + "\\pois\\" + Utilities.SERVER_LOC_RES + "\\" +
					Utilities.SERVER_LOC_THRESHOLD + "\\" + poiID + ".poi";
			poiFile = new File(poiPath);
			if (poiFile.exists()) {
				storedPOIs.put(entryKey, loadPointsFromFile(poiPath));
				Utilities.print("Updated (poi): " + entryKey + " (size: " + storedPOIs.size() + ")");
			}
			else {
				storedPOIs.remove(entryKey);
				Utilities.print("Removed (poi): " + entryKey + " (size: " + storedPOIs.size() + ")");
			}
//			POIsToRemove.add(entryKey);
//			Utilities.saveString(Utilities.spaceDir + "POIchangelog.ans", joPOIs.toJSONString());
		}
//		for (String key : POIsToRemove) {
//			joPOIs.remove(key);
//		}
		Utilities.loadingPOIs = false;
	}

	//! Loads the changed Tags (since the last update)
	@SuppressWarnings({"unchecked"})
	public static void updateTags() {
		Utilities.loadingTags = true;
		JSONObject joTags = Utilities.loadJSONObject(Utilities.spaceDir + "TAGchangelog.ans");
		cleanChangelog("TAGchangelog.ans");
		String entryKey, spaceID, tagID, poiPath;
		File poiFile;

		for (Entry<String, String> entry : (Set<Entry<String, String>>) joTags.entrySet()) {
			entryKey = entry.getKey();
			spaceID = entryKey.substring(0, 2);
			tagID = entryKey.substring(2, 5);

			poiPath = Utilities.getTagDir(spaceID) + "all\\" + tagID + "\\" + tagID + ".poi";
			poiFile = new File(poiPath);
			if (poiFile.exists()) {
				storedTags.get(spaceID).put(tagID, loadPointsFromFile(poiPath));
				Utilities.print("Updated (tag): " + entryKey + " (size: " + storedTags.get(spaceID).size() + ")");
			}
			else {
				storedPOIs.remove(entryKey);
				Utilities.print("Removed (tag): " + entryKey + " (size: " + storedTags.get(spaceID).size() + ")");
			}
		}
		Utilities.loadingTags = false;
	}

	//! Removes all the entries in the POI-changelog
	public static void cleanChangelog(String changelog) {
		Utilities.saveString(Utilities.spaceDir + changelog, new JSONObject().toJSONString());
	}

	//! Casts an Object array to an Interest Point array
	private static List<InterestPoint> toInterestPointList(Object[] objArray) {
		List<InterestPoint> iptList = new ArrayList<InterestPoint>();
		for (Object obj : objArray) {
			iptList.add((InterestPoint)obj);
		}
		return iptList;
	}
	
	//! Converts map to list
	private static List<Match> convertToList(Map<String, Match> map) {
		List<Match> matches = new ArrayList<Match>();
		for (Entry<String, Match> entry : map.entrySet()) {
			matches.add(new Match(entry.getValue().quantity, entry.getValue().ocurrences, entry.getKey()));
		}
		Collections.sort(matches);
		return matches;
	}

	public static void speedTest() {
		try{
		long begin, end;
//		begin = System.currentTimeMillis();
		String imgPath1 = "D:\\Tests\\Experimento007\\003.jpg";
		String imgPath2 = "D:\\Tests\\Experimento007\\012.jpg";
		List<InterestPoint> points1 = SurfUtil.getInterestPoints(imgPath1, Utilities.TAG_THRESHOLD);
		List<InterestPoint> points2 = SurfUtil.getInterestPoints(imgPath2, Utilities.TAG_THRESHOLD);
		begin = System.currentTimeMillis();
		Map<InterestPoint, InterestPoint> matchedPoints = getMatches(points1, points2);
		end = System.currentTimeMillis() - begin;
		System.out.println("IPs matched: " + matchedPoints.size() + ", time: " + end / 1000d + ", " +
				points1.size() + " " + points2.size());

		BufferedImage tmp1 = ImageIO.read(new File(imgPath1));
		int w1 = tmp1.getWidth();
		int h1 = tmp1.getHeight();
		BufferedImage tmp2 = ImageIO.read(new File(imgPath2));
		int w2 = tmp2.getWidth();
		int h2 = tmp2.getHeight();

		BufferedImage bi2 = new BufferedImage(w1+w2,Math.max(h1, h2),BufferedImage.TYPE_INT_ARGB);
		Graphics2D g = bi2.createGraphics();
		g.setColor(Color.black);
		g.fillRect(0, 0, bi2.getWidth(), bi2.getHeight());
		g.drawImage(tmp1, 0, 0, null);
		g.drawImage(tmp2, w1, 0, null);


		g.setStroke(new BasicStroke(1f));
		for (Entry<InterestPoint, InterestPoint> entry : matchedPoints.entrySet()) {
			InterestPoint ip1 = entry.getKey();
			InterestPoint ip2 = entry.getValue();
			g.setColor(Color.blue);
			g.drawOval((int)ip1.getX() - 2, (int)ip1.getY() - 2, 4, 4);
			g.drawOval(w1 + (int)ip2.getX() - 2, (int)ip2.getY() - 2, 4, 4);
			g.setColor(Color.red);
			g.drawLine((int)ip1.getX(), (int)ip1.getY(),
					w1 + (int)ip2.getX(), (int)ip2.getY());
		}

		g.dispose();

		JFrame f2 = new JFrame("matches2");
		JLabel l2 = new JLabel(new ImageIcon(bi2));
		f2.getContentPane().add(l2);
		f2.setSize(w1 + w2 + 300, h1 + 50);
//			f2.setBounds(0, 0, bi2.getWidth() + 50, bi2.getHeight() + 30);
		f2.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
		f2.setVisible(true);
			} catch (IOException e) {

		}
	}

	/*public static void scaleCCheckTest() {
		try {
			String imgPath1 = "D:\\Tests\\Experimento007\\002.jpg";
			String imgPath2 = "D:\\Tests\\Experimento007\\038.jpg";
			List<InterestPoint> points1 = SurfUtil.getInterestPoints(imgPath1, Utilities.TAG_THRESHOLD);
			List<InterestPoint> points2 = SurfUtil.getInterestPoints(imgPath2, Utilities.TAG_THRESHOLD);

			Map<InterestPoint, InterestPoint> matchedPoints = getMatches(points1, points2);

			long begin, end;
			begin = System.currentTimeMillis();
			ArrayList<Scale> scales = ScaleConsistencyCheck.compute(matchedPoints);
			end = System.currentTimeMillis() - begin;

			System.out.println("Check time = " + end / 1000d);

			BufferedImage tmp1 = ImageIO.read(new File(imgPath1));
			int w1 = tmp1.getWidth();
			int h1 = tmp1.getHeight();
			BufferedImage tmp2 = ImageIO.read(new File(imgPath2));
			int w2 = tmp2.getWidth();
			int h2 = tmp2.getHeight();

			BufferedImage bi2 = new BufferedImage(w1+w2,Math.max(h1, h2),BufferedImage.TYPE_INT_ARGB);
			Graphics2D g = bi2.createGraphics();
			g.setColor(Color.black);
			g.fillRect(0, 0, bi2.getWidth(), bi2.getHeight());
			g.drawImage(tmp1, 0, 0, null);
			g.drawImage(tmp2, w1, 0, null);


			g.setStroke(new BasicStroke(1f));
			for (Entry<InterestPoint, InterestPoint> entry : matchedPoints.entrySet()) {
				InterestPoint ip1 = entry.getKey();
				InterestPoint ip2 = entry.getValue();
				g.setColor(Color.blue);
				g.drawOval((int)ip1.getX() - 2, (int)ip1.getY() - 2, 4, 4);
				g.drawOval(w1 + (int)ip2.getX() - 2, (int)ip2.getY() - 2, 4, 4);
				g.setColor(Color.red);
				g.drawLine((int)ip1.getX(), (int)ip1.getY(),
						w1 + (int)ip2.getX(), (int)ip2.getY());
			}

			System.out.println("Size " + matchedPoints.size());
			g.setStroke(new BasicStroke(3f));
			for (Scale scale : scales) {
				if (!scale.inConsensusSet) {
					matchedPoints.remove(scale.ipQ);
					InterestPoint ip1 = scale.ipQ;
					InterestPoint ip2 = scale.ipD;
					g.setColor(Color.GREEN);
					g.drawOval((int)ip1.getX() - 3, (int)ip1.getY() - 3, 6, 6);
					g.drawOval(w1 + (int)ip2.getX() - 3, (int)ip2.getY() - 3, 6, 6);
				}
			}
			System.out.println("Size " + matchedPoints.size());


			g.dispose();

			JFrame f2 = new JFrame("matches2");
			JLabel l2 = new JLabel(new ImageIcon(bi2));
			f2.getContentPane().add(l2);
			f2.setSize(w1 + w2 + 300, h1 + 50);
//			f2.setBounds(0, 0, bi2.getWidth() + 50, bi2.getHeight() + 30);
			f2.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
			f2.setVisible(true);

//			System.out.println("Matches:" + matchedPoints.size() + ", " + end / 1000d);
		} catch (IOException e) {

		}
	}*/

	public static void kdTreeTest(){
		try {
			String imgPath1 = "D:\\Tests\\Experimento007\\001.jpg";
			String imgPath2 = "D:\\Tests\\Experimento007\\006.jpg";
			List<InterestPoint> points1 = SurfUtil.getInterestPoints(imgPath1, Utilities.TAG_THRESHOLD);
			List<InterestPoint> points2 = SurfUtil.getInterestPoints(imgPath2, Utilities.TAG_THRESHOLD);

			long begin, end;

			InterestPoint[] points2Arr = points2.toArray(new InterestPoint[0]);
			// create kd-trees
			KDNode kdRoot = KDTree.build(points2Arr, points2Arr.length);

			begin = System.currentTimeMillis();
			InterestPoint[] points1Arr = points1.toArray(new InterestPoint[0]);
			InterestPoint[] pointsSingle = new InterestPoint[1];
			pointsSingle[0] = points1Arr[0];
//			int numMatches = matchWithKDTree(points1Arr, points1Arr.length, kdRoot);
			int numMatches = matchWithKDTree(pointsSingle, 1, kdRoot);

//			kdRoot = KDTree.build(points1Arr, points1Arr.length);
//			int numMatches2 = matchWithKDTree(points2Arr, points2Arr.length, kdRoot);

//			int numMatches = getMatches(points1Arr, points1Arr.length, points2Arr, points2Arr.length);
			end = System.currentTimeMillis() - begin;
			System.out.println("Matches:" + numMatches/* + ", " + numMatches2*/ + ", " + end / 1000d);

			BufferedImage tmp1 = ImageIO.read(new File(imgPath1));
			int w1 = tmp1.getWidth();
			int h1 = tmp1.getHeight();
			BufferedImage tmp2 = ImageIO.read(new File(imgPath2));
			int w2 = tmp2.getWidth();
			int h2 = tmp2.getHeight();

			BufferedImage bi = new BufferedImage(w1+w2,Math.max(h1, h2),BufferedImage.TYPE_INT_ARGB);
			Graphics2D g = bi.createGraphics();
			g.setColor(Color.black);
			g.fillRect(0, 0, bi.getWidth(), bi.getHeight());
			g.drawImage(tmp1, 0, 0, null);
			g.drawImage(tmp2, w1, 0, null);


			g.setStroke(new BasicStroke(1f));
			for (InterestPoint feature : points1Arr) {
				if(feature.fwdMatch != null/* && feature == feature.fwdMatch.fwdMatch*/) {
//					if (feature.fwdMatch.fwdMatch != null)
//					System.out.println("x:" + feature.getX() + ", y:" + feature.getY() +
//							"fx:" + feature.fwdMatch.getX() + ", fy:" + feature.fwdMatch.getY() +
//							"ffx:" + feature.fwdMatch.fwdMatch.getX() + ", ffy:" + feature.fwdMatch.fwdMatch.getY());
//

					g.setColor(Color.blue);
					g.drawOval((int)feature.getX() - 2, (int)feature.getY() - 2, 4, 4);
					g.drawOval(w1 + (int)feature.fwdMatch.getX() - 2, (int)feature.fwdMatch.getY() - 2, 4, 4);
					g.setColor(Color.red);
					g.drawLine((int)feature.getX(), (int)feature.getY(),
							w1 + (int)feature.fwdMatch.getX(), (int)feature.fwdMatch.getY());
				}
			}

			g.dispose();

			JFrame f = new JFrame("matches");
			JLabel l = new JLabel(new ImageIcon(bi));
			f.getContentPane().add(l);
			f.setBounds(0, 0, bi.getWidth() + 20, bi.getHeight() + 30);
			f.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
			f.setVisible(true);


			begin = System.currentTimeMillis();
			ArrayList<InterestPoint> pointsSingleList = new ArrayList<InterestPoint>();
			pointsSingleList.add(points1.get(0));
			Map<InterestPoint, InterestPoint> matchedPoints = findMatches(pointsSingleList, points2);
//			Map<InterestPoint, InterestPoint> matchedPoints = getMatches(points1, points2);
//			Map<InterestPoint, InterestPoint> matchedPoints = findMatches(points1, points2);
			end = System.currentTimeMillis() - begin;

			System.out.println("Matches:" + matchedPoints.size() + ", " + end / 1000d);


			BufferedImage bi2 = new BufferedImage(w1+w2,Math.max(h1, h2),BufferedImage.TYPE_INT_ARGB);
			g = bi2.createGraphics();
			g.setColor(Color.black);
			g.fillRect(0, 0, bi2.getWidth(), bi2.getHeight());
			g.drawImage(tmp1, 0, 0, null);
			g.drawImage(tmp2, w1, 0, null);


			g.setStroke(new BasicStroke(1f));
			for (Entry<InterestPoint, InterestPoint> entry : matchedPoints.entrySet()) {
				InterestPoint ip1 = entry.getKey();
				InterestPoint ip2 = entry.getValue();
				g.setColor(Color.blue);
				g.drawOval((int)ip1.getX() - 2, (int)ip1.getY() - 2, 4, 4);
				g.drawOval(w1 + (int)ip2.getX() - 2, (int)ip2.getY() - 2, 4, 4);
				g.setColor(Color.red);
				g.drawLine((int)ip1.getX(), (int)ip1.getY(),
						w1 + (int)ip2.getX(), (int)ip2.getY());
			}

			g.dispose();

			JFrame f2 = new JFrame("matches2");
			JLabel l2 = new JLabel(new ImageIcon(bi2));
			f2.getContentPane().add(l2);
			f2.setBounds(0, 0, bi2.getWidth() + 20, bi2.getHeight() + 30);
			f2.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
			f2.setVisible(true);

		} catch (IOException e) {
			
		}
	}

	public static int matchWithKDTree(InterestPoint[] feat1, int n1, KDNode kdRoot) {
		InterestPoint[] neighbors = new InterestPoint[4];
		InterestPoint feat;
		double d0, d1, d2, d3;
		int i, k, m = 0;

		for(i = 0; i < n1; i++) {
			feat = feat1[i];
			k = KDTree.kdTreeBbfKnn(kdRoot, feat, 4, neighbors, KDTREE_BBF_MAX_NN_CHKS);
			if(k == 4) {
				d0 = InterestPoint.descriptorSquaredDistance(feat, neighbors[0]);
				d1 = InterestPoint.descriptorSquaredDistance(feat, neighbors[1]);
				d2 = InterestPoint.descriptorSquaredDistance(feat, neighbors[2]);
				d3 = InterestPoint.descriptorSquaredDistance(feat, neighbors[3]);

				System.out.println("test point: x=" + feat.getX() + ", y=" + feat.getY());
				System.out.println("d0=" + d0 + " is better than d1=" + d1 + " is better than d2=" + d2 + " is better than d3=" + d3);

//				System.out.println("test point: x=" + feat.getX() + ", y=" + feat.getY());
//				System.out.println("Best match: x=" + neighbors[0].getX() + ", y=" + neighbors[0].getY() + ", d=" + d0);
				if(d0 < d1 * NN_SQ_DIST_RATIO_THR) {
					m++;
					feat1[i].fwdMatch = neighbors[0];
				}
			}
		}

		return m;
	}

	public static int getMatches(InterestPoint[] feat1, int n1, InterestPoint[] feat2, int n2) {
		// build kd-tree with the feat2
		KDNode kdRoot = KDTree.build(feat2, n2);
		// match feat1 with the kd-tree
		return matchWithKDTree(feat1, n1, kdRoot);
	}
}